Currently, various communication systems including wireless communication systems (such as mobile telephone systems and wireless LAN systems) are being used. (LAN stands for local area network.) In the communication systems, bit errors can occur when signals are transmitted through transmission lines. In order to compensate for the bit errors, it is possible to use the error-correcting coding technology in transmission devices and reception devices. The transmission devices convert data into error-correcting codes, and transmit the error-correcting codes. The reception devices receive and decode the error-correcting codes. Even when the received data contain bit errors, bit errors not exceeding a certain level can be corrected in the decoding process.
Some types of error-correcting codes such as convolutional codes (CC) and convolutional turbo codes (CTC) are generated by convolutional encoding. The internal state of an encoder performing convolutional encoding transitions on the basis of an input signal, and the output signal of the encoder is determined on the basis of the input signal before being encoded and the internal state of the encoder. That is, the output signal of the encoder outputted in response to an input signal depends on one or more input signals previously inputted into the encoder as well as the current input signal. The convolutional encoded data can be decoded, for example, by using the Viterbi decoding algorithm. (See, for example, Japanese Laid-open Patent Publication No. 2000-278144.)
In some types of convolutional encoding, a plurality of operations are performed on a data block (which is a unit of data to be encoded). For example, according to the tail-biting convolutional encoding, in order to allow the cyclic state transition, the final state of the encoder is determined by preliminarily encoding the data block as preprocessing, and then the initial state is determined on the basis of the final state. Thereafter, the same data block is encoded again by using the determined initial state, and the encoded data block is outputted.
As described above, the calculational load of the convolution can become heavy. If a great number of data blocks to be encoded are inputted into an encoder in a short time, the encoder cannot encode the great number of data blocks on a real-time basis, so that the encoding can be delayed or a buffer overflow can occur.